package 每日一题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-28
 **/

public class No869重新排序得到2的幂 {

    /**
     * 给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
     * 如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
     * <p>
     * 示例 1：
     * 输入：1
     * 输出：true
     * 示例 2：
     * 输入：10
     * 输出：false
     * 示例 3：
     * 输入：16
     * 输出：true
     * 示例 4：
     * 输入：24
     * 输出：false
     * 示例 5：
     * 输入：46
     * 输出：true
     *  
     * 提示：
     * 1 <= N <= 10^9
     */

    // 存入数组, 0 ~ 9, 元素意义为当前下标所对应的[单个数字字符]的个数
    private static List<int[]> list = new ArrayList<>(30);

    static {

        int num = 1;

        int[] zeroArr = new int[10];
        zeroArr[1] = 1;
        list.add(zeroArr);

        for (int i = 0; i < 30; i++) {
            num <<= 1;
            int[] arr = new int[10];
            int tempNum = num;
            while (tempNum != 0) {
                int item = tempNum % 10;
                tempNum /= 10;
                arr[item]++;
            }
            list.add(arr);
        }

    }

    public boolean reorderedPowerOf2(int n) {

        int[] arr = new int[10];
        while (n != 0) {
            int item = n % 10;
            n /= 10;
            arr[item]++;
        }

        for (int[] ints : list) {
            if (Arrays.equals(ints, arr)) {
                return true;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        No869重新排序得到2的幂 n = new No869重新排序得到2的幂();
        System.out.println(n.reorderedPowerOf2(1));
    }

}
